package com.jacklei.ch18;

/*
* 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

 

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]
 

提示：
1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
所有[ai, bi] 互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/course-schedule-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

import sun.security.util.Length;

import java.util.*;

public class CourseScheduleII {
    public static void main(String[] args) {
        CourseScheduleII c= new CourseScheduleII();
        int[] order = c.findOrder3(3, new int[][]{
                //{1, 0}, {2, 0}, {3, 1}, {3, 2}
                //{0,1}
                {0,1},{1,0},{1,2}
        });
        for (int i : order) {
            System.out.println(i);
        }
    }
    public int[] findOrder1(int numCourses, int[][] prerequisites) {
        int[] result= new int[numCourses];
        if(prerequisites.length == 0){
            for (int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
            if(map.containsKey(prerequisite[0])){
                List<Integer> list = map.get(prerequisite[0]);
                list.add(prerequisite[1]);
                map.put(prerequisite[0],list);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(prerequisite[1]);
                map.put(prerequisite[0],list);
            }
        }
        HashSet<Integer> set = new HashSet<>();
        int p = 0;
        for (Map.Entry<Integer, List<Integer>> o: map.entrySet()) {
            Integer key = o.getKey();
            Stack<Integer>  stack = new Stack();
            stack.add(key);

            while (map.containsKey(key)) {
                List<Integer> keyList = map.get(key);
                for (Integer key0 : keyList) {
                    if (!stack.contains(key0)) {
                        stack.add(key0);
                    } else {
                        return result;
                    }
                }

            }
            while (!stack.isEmpty()) {
                key = stack.pop();
                if (!set.contains(key)) {
                    set.add(key);
                    result[p++] = key;
                    if (p == result.length)
                        return result;
                }
            }

        }

        for (int i = p; i < result.length; i++) {
            result[i] = i;
        }


        return result;
    }
    //广度遍历
    public int[] findOrder2(int numCourses, int[][] prerequisites) {
        int [] result = new int[numCourses];
        if(prerequisites.length == 0){
            for (int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        HashMap<Integer,Info> map = new HashMap();
        for (int[] prerequisite : prerequisites) {

            Info o1 ;Info o2 ;
            if(map.containsKey(prerequisite[0])){
                o1 = map.get(prerequisite[0]);
            }else {
                o1 = new Info(prerequisite[0]);
                map.put(prerequisite[0],o1);
            }

            if(map.containsKey(prerequisite[1])){
                o2 = map.get(prerequisite[1]);
            }else {
                o2 = new Info(prerequisite[1]);
                map.put(prerequisite[1],o2);
            }
            o1.down.add(o2);
            o2.up.add(o1);
        }
        // 找到头(可能是多个头)
        List<Info> head = new ArrayList<>();
        for (Map.Entry<Integer, Info> o : map.entrySet()) {
            if(o.getValue().down.size() == 0)
                head .add(map.get(o.getKey()));
        }

        if(head.size() == 0)return new int[]{};
        HashSet<Info> set = new HashSet(); //查看是否有环
        HashSet<Integer> setv = new HashSet();
        //广度优先遍历
        int p = 0;
        Queue<Info> queue = new LinkedList<>();
        for (Info info : head) {
            queue.add(info);
            set.add(info);
        }
        while (!queue.isEmpty()){
            Info poll = queue.poll();
            poll.sort();
            for (int i = 0; i < poll.up.size(); i++) {
                Info info = poll.up.get(i);
                if(!set.contains(info)) {
                    set.add(info);
                    queue.add(info);
                }else if (info.up.size() != 0){

                    return new int[]{};
                }
            }
            if(p < result.length){
                result[p++] = poll.value;
                setv.add(poll.value);
            }

        }
        //广度优先遍历

        for (int i = 0; i < result.length && p < result.length; i++) {
            if(!setv.contains(i)){
                result[p++] = i;
            }
        }



        return result;
    }

    //
    List<List<Integer>> edges;
    // 存储每个节点的入度
    int[] indeg;
    // 存储答案
    int[] result;
    // 答案下标
    int index;
    public int[] findOrder3(int numCourses, int[][] prerequisites) {
        edges = new ArrayList<List<Integer>>();
        for (int i = 0; i < numCourses; i++) {
            edges.add(new ArrayList<Integer>());
        }
        indeg = new int[numCourses];
        result = new int[numCourses];
        index = 0;
        for (int[] info : prerequisites) {
            edges.get(info[1]).add(info[0]);
            ++indeg[info[0]];
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if(indeg[i] == 0) {
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()) {
            int u = queue.poll();
            result[index++] = u;
            for (Integer v : edges.get(u)) {
                --indeg[v];
                // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
                if(indeg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        if(index != numCourses) {
            return new int[0];
        }
        return result;
    }

    class Info {
        int value;
        List<Info> up =  new ArrayList<Info>();
        List<Info> down = new ArrayList<Info>();

        public Info(int value) {
            this.value = value;
        }
        public void sort(){
            Collections.sort(up, new Comparator<Info>() {
                @Override
                public int compare(Info o1, Info o2) {
                    return (o2.up.size() - o2.down.size() - (o1.up.size() - o1.down.size()));
                }
            });
        }
    }
}
